package BinaryTree;
/*
* 二叉搜索树与双向链表
* 把二叉树变成双向循环链表
*
* 喵喵喵!!!
* */
public class Offer36treeToDoublyList {
    TreeNode first=new TreeNode(Integer.MAX_VALUE);
    TreeNode tail=new TreeNode(Integer.MIN_VALUE);
    TreeNode pre=new TreeNode();
    public TreeNode treeToDoublyList(TreeNode root) {
        if(root==null){
            return root;
        }
        dfs(root);
        first.left=tail;
        tail.right=first;
        return first;
    }

    private void dfs(TreeNode root) {
        if(root==null){
            return;
        }
        dfs(root.left);
        pre.right=root;
        root.left=pre;
        pre=root;
        if(root.val<first.val){
            first=root;
        }
        if(root.val>tail.val){
            tail=root;
        }
        dfs(root.right);
    }
}
